#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

void bubbleSort(int *a, int len);

void selectionSort(int *a, int len);

void InsertionSort(int *a, int len);

void shellSort(int *a, int len);

void quickSort(int *arr, int left, int right);

void heapSort(int *arr, int n);

void swap(int *arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void printArray(int *array)
{
    for (int i = 0; i < SIZE; i++)
    {
        printf("%d\t", array[i]);
    }
    printf("\n");
}

int isMaxHeap(int *array, int size, int n)
{
    int l = n * 2 + 1;
    int r = n * 2 + 2;
    if (r < size)
    {
        if (l < size)
        {
            if (array[n] > array[l] && array[n] > array[r] && isMaxHeap(array, size, l) &&
                isMaxHeap(array, size, r))
            {
                return 1;
            }
            printf("\np[%d].%d l[%d].%d r[%d].%d is error\n", n, array[n], l, array[l], r, array[r]);
            return 0;
        }
        if (array[n] > array[r] && isMaxHeap(array, size, r))
        {
            return 1;
        }
        printf("\np[%d].%d l[%d].%d is error\n", n, array[n], l, array[l]);
        return 0;
    }
    if (l < size)
    {
        if (array[n] > array[l] && isMaxHeap(array, size, l))
        {
            return 1;
        }
        printf("\np[%d].%d  l[%d].%d  is error\n", n, array[n], l, array[l]);
        return 0;
    }
    return 1;
}
int main()
{
    int array[SIZE];
    srand(time(NULL));

    printf("%d", 1 / 2);
    for (int i = 0; i < SIZE; i++)
    {
        array[i] = rand() % 100 + 10;
    }

    printf("before the sort of array\n");
    printArray(array);
    // shellSort(array, SIZE);
    heapSort(array, SIZE);
    printf("after the sort of array\n");
    printArray(array);
    if (isMaxHeap(array, SIZE, 0))
        printf("\nthis is max heap\n");
    else
        printf("\nthis isn't max heap\n");
}

void bubbleSort(int *a, int len)
{
    int i, j, k, temp;
    for (i = 0; i < len - 1; i++)
    {
        for (j = len - 1; j > 1; j--)
        {
            if (a[j - 1] > a[j])
            {
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

void selectionSort(int *a, int len)
{
    int i, j, k, h, temp;
    for (i = 0; i < len; i++)
    {
        k = i;
        for (j = i + 1; j < len; j++)
        {
            if (a[j] < a[k])
                k = j;
            if (j != i)
            {
                temp = a[i];
                a[i] = a[k];
                a[k] = temp;
            }
        }
    }
}

void InsertionSort(int *a, int len)
{
    int i, j, t, h;
    for (i = 1; i < len; i++)
    {
        t = a[i];
        j = i - 1;
        while (i >= 0 && t < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = t;
    }
}

void shellSort(int *a, int len)
{
    int i, j, h;
    int r, temp;
    for (r = len / 2; r >= 1; r /= 2)
    {
        for (int i = r; i < len; i++)
        {
            temp = a[i];
            j = i - r;
            while (j >= 0 && temp < a[j])
            {
                a[j + r] = a[j];
                j -= r;
            }
            a[j + r] = temp;
        }
    }
}

void quickSort(int *arr, int left, int right)
{
    int f, t;
    int rtemp, ltemp;
    ltemp = left;
    rtemp = right;
    f = arr[(left + right) / 2];
    while (ltemp < rtemp)
    {
        while (arr[ltemp] < f)
        {
            ++ltemp;
        }
        while (arr[rtemp] > f)
        {
            --rtemp;
        }
        if (ltemp <= rtemp)
        {
            t = arr[ltemp];
            arr[ltemp] = arr[rtemp];
            arr[rtemp] = t;
            --rtemp;
            ++ltemp;
        }
        if (ltemp == rtemp)
        {
            ltemp++;
        }
        if (left < rtemp)
        {
            quickSort(arr, left, ltemp - 1);
        }
        if (ltemp < right)
        {
            quickSort(arr, rtemp + 1, right);
        }
    }
}

void percolateDown(int *array, int p)
{
    int l, r, max, temp;
    l = 2 * p + 1;
    r = l + 1;
    max = p;
    if (l < SIZE && array[l] > array[max])
        max = l;
    if (r < SIZE && array[r] > array[max])
        max = r;
    if (max != p)
    {
        swap(array, max, p);
        percolateDown(array, max);
    }
}
void heapSort(int *array, int n)
{
    for (int i = n - 1; i >= 0; i--)
    {
        percolateDown(array, i);
    }

    for (int i = n - 1; i > 0; i--)
    {
        swap(array, 0, i);
        int k = 0;
        while ((2 * k + 1) < i)
        {
            int l = 2 * k + 1;
            int r = l + 1;
            if (r < i && array[l] < array[r])
                l++;
            if (array[k] < array[l])
            {
                swap(array, k, l);
                k = l;
            }
            else
                break;
        }
    }
}
